#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include <vector>
#include <unordered_map>
#include <queue>
//class Solution {
//public:
//    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
//        if (prerequisites.size() == 0)
//            return true;
//        unordered_map<int, vector<int>> edges;
//        vector<int> in(numCourses, 0);
//        int m = prerequisites.size();
//        int n = prerequisites[0].size();
//        for (int i = 0; i < m; i++)
//        {
//            edges[prerequisites[i][1]].push_back(prerequisites[i][0]);
//            in[prerequisites[i][0]]++;
//        }
//        queue<int> q;
//        for (int i = 0; i < numCourses; i++)
//        {
//            if (in[i] == 0)
//                q.push(i);
//        }
//
//        while (!q.empty())
//        {
//            int size = q.size();
//            for (int i = 0; i < size; i++)
//            {
//                int top = q.front();
//                q.pop();
//                for (auto& e : edges[top])
//                {
//                    in[e]--;
//                    if (in[e] == 0)
//                        q.push(e);
//                }
//            }
//        }
//        for (int i = 0; i < numCourses; i++)
//        {
//            if (in[i] != 0)
//                return false;
//        }
//        return true;
//    }
//};

//class Solution {
//public:
//    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
//        vector<int> ret;
//        int m = prerequisites.size();
//        if (m == 0)
//        {
//            for (int i = 0; i < numCourses; i++)
//                ret.push_back(i);
//
//            return ret;
//        }
//        unordered_map<int, vector<int>> edges;
//        vector<int> in(numCourses, 0);
//        for (int i = 0; i < m; i++)
//        {
//            int a = prerequisites[i][0], b = prerequisites[i][1];
//            edges[b].push_back(a);
//            in[a]++;
//        }
//        queue<int> q;
//        for (int i = 0; i < numCourses; i++)
//        {
//            if (in[i] == 0)
//                q.push(i);
//        }
//        while (!q.empty())
//        {
//            int tmp = q.front();
//            q.pop();
//            ret.push_back(tmp);
//            //cout<<tmp<<endl;
//            for (auto& e : edges[tmp])
//            {
//                in[e]--;
//                if (in[e] == 0)
//                    q.push(e);
//            }
//        }
//        for (int i = 0; i < numCourses; i++)
//        {
//            if (in[i] != 0)
//                return {};
//        }
//        return ret;
//    }
//};
#include <unordered_set>
class Solution {
public:
    string alienOrder(vector<string>& words) {
        int size = words.size();
        unordered_map<char, unordered_set<char>> edges;
        unordered_map<char, int> in;
        for (int i = 0; i < size; i++)
        {
            for (auto e : words[i])
                in[e] = 0;
        }
        for (int i = 0; i < size - 1; i++)
        {
            for (int j = i + 1; j < size; j++)
            {
                int cur = 0;
                while (cur < words[i].size() && cur < words[j].size())
                {
                    if (words[i][cur] != words[j][cur])
                    {
                        char a = words[i][cur], b = words[j][cur];
                        if (edges[a].count(b) == 0)
                        {
                            edges[a].insert(b);
                            in[b]++;
                        }
                        break;
                    }
                    cur++;
                }
                if (cur == words[j].size() && cur < words[i].size())
                    return "";
            }

        }
        string ret;
        queue<char> q;
        for (auto& e : in)
        {
            if (e.second == 0)
                q.push(e.first);
        }
        while (!q.empty())
        {
            char ch = q.front();
            q.pop();
            ret += ch;
            for (auto e : edges[ch])
            {
                in[e]--;
                if (in[e] == 0)
                    q.push(e);
            }
        }
        for (auto& e : in)
        {
            if (e.second != 0)
                return "";
        }
        return ret;

    }
};
int main()
{
    vector<vector<int>> prerequisites = { {0,1} };
    //Solution().canFinish(2,prerequisites);
    vector<string> n = { "wrt","wrf","er","ett","rftt" };
    Solution().alienOrder(n);
    //Solution().findOrder(2, prerequisites);
	return 0;
}